package org.liaohailong.victor;

import androidx.annotation.NonNull;

/**
 * Author: liaohailong
 * Time: 2021/11/25 10:25
 * Describe: 链表
 */
public class LinkedStudy {

    // 反转链表 - 非递归
    public static ListNode reverse1(@NonNull ListNode head) {
        ListNode curr = head;
        ListNode prev = null;
        while (curr != null) {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }

    // 反转链表 - 递归
    public static ListNode reverse2(@NonNull ListNode head) {
        return _reverse2(head, null);
    }

    private static ListNode _reverse2(ListNode curr, ListNode prev) {
        if (curr == null) return prev;
        ListNode next = curr.next;
        curr.next = prev;
        return _reverse2(next, curr);
    }


    public static ListNode generate(int[] arr) {
        ListNode head = null;
        ListNode curr = null;
        for (int i : arr) {
            ListNode next = new ListNode(i, null);
            if (head == null) {
                head = next;
                curr = head;
            } else {
                curr.next = next;
                curr = curr.next;
            }
        }
        return head;
    }

    public static void print(ListNode head) {
        if (head == null) {
            System.out.println("[]");
            return;
        }
        StringBuilder sb = new StringBuilder();
        sb.append("[");
        ListNode curr = head;
        while (curr != null) {
            sb.append(curr.value);
            if (curr.next != null) sb.append(",");
            curr = curr.next;
        }
        sb.append("]");
        System.out.println(sb.toString());
    }

    public static final class ListNode {
        public int value;
        public ListNode next;

        public ListNode(int value, ListNode next) {
            this.value = value;
            this.next = next;
        }
    }
}
